package com.dexter.year2023.charpter3_array.level3.topic3_1数组中出现次数超过一半的数字;

import java.util.HashMap;

/**
 * 数组中出现次数超过一半的数字
 * 来源：剑指offer 39. P205
 *
 * @author Dexter
 */
public class MoreThanHalfNum {
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 2, 2, 2, 5, 4, 2};
        // 法1：用HashMap统计次数，时间复杂度 O(n) 空间复杂度 O(n)
        int res = moreThanHalfNumByHashMap(a);
        System.out.println(res);
        // 法2：0标记更换数字，时间复杂度 O(n) 空间复杂度 O(1)（墙裂推荐！！！）
        int res2 = moreThanHalfNum(a);
        System.out.println(res2);
    }

    /**
     * 法1：用HashMap统计次数
     */
    public static int moreThanHalfNumByHashMap(int[] nums) {
        if (nums == null) {
            return 0;
        }
        HashMap<Integer, Integer> res = new HashMap<>();
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            // 数字，出现次数
            res.put(nums[i], res.getOrDefault(nums[i], 0) + 1);
            // 次数超过一半
            if (res.get(nums[i]) > len / 2) {
                return nums[i];
            }
        }
        return 0;
    }

    /**
     * 法2：通过+1 -1统计次数，0时更换候选人
     *
     * @param nums
     * @return
     */
    public static int moreThanHalfNum(int[] nums) {
        int count = 0;
        // 当前擂台上数字
        Integer lord = null;
        for (int num : nums) {
            if (count == 0) {
                // 新的擂主
                lord = num;
            }
            // 数字相同 +1 不同 -1
            count += (num == lord) ? 1 : -1;
        }
        return lord;
    }
}
